/*
 * @lc app=leetcode.cn id=797 lang=cpp
 *
 * [797] 所有可能的路径
 */

// @lc code=start
class Solution
{
public:
  typedef vector<vector<int>> Matrix;

  int n;

  vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph)
  {
    this->n = graph.size();
    Matrix path;
    vector<int> tmp;
    DFS(graph, path, tmp, 0);
    return path;
  }

  void DFS(Matrix& graph, Matrix& path, vector<int>& tmp, int vertex)
  {
    tmp.push_back(vertex);
    if (vertex == n - 1) {
      path.push_back(tmp);
    }
    else {
      for (int& v : graph[vertex])
        DFS(graph, path, tmp, v);
    }
    tmp.pop_back();
  }
};
// @lc code=end
